452. 用最少数量的箭引爆气球

Similar Question

435. 无重叠区间

Solution Tips

方案一: 排序 + 贪心

var findMinArrowShots = function (points) {
    // 从左到右看, 要优先击破能击破的, 先从左到右进行一次排序
    // 求出每个气球的交集? 如果有交集就继续求下一个气球有没有交集, 没有了就直接击破
    // 具体的击破位置并不重要
    // left 相同的需要再依据 right 排序
    points.sort((a, b) => {
        if (a[0] - b[0] === 0) {
            return a[1] - b[1];
        }
        else return a[0] - b[0];
    });
    let i = 0;
    let res = 0;
    // 左和右要同时判断, 最大的射击范围是已经纳入考虑的最小的 right, 不用考虑 left ? 不用, 最小的 right 一定能射穿
    while (i < points.length) {
        let right = points[i][1];
        let j = i + 1;
        while (j < points.length) {
            let l = points[j][0];
            if (right >= l) {
                // 纳入
                right = Math.min(right, points[j][1]);
                j++;
            }
            else {
                break;
            }
        }
        // 有交集的气球都一次射穿即可
        res++;
        i = j;
    }

    return res;
};
console.log(findMinArrowShots([[0,9],[1,8],[7,8],[1,6],[9,16],[7,13],[7,10],[6,11],[6,9],[9,13]]))

方案一优化:

控制流程分支代码优化

这里的 j 本质上也是 i , 所以其实是可以简化成一个循环的, 只不过两个变量的更加贴近模拟的真实情况

方法一种最终的就是 right 值, 所以排序也可以直接按照 right 值来

var findMinArrowShots = function(points) {
    if (!points.length ) {
        return 0;
    }

    points.sort((a, b) => a[1] - b[1]);
    let pos = points[0][1]
    let ans = 1;
    for (let balloon of points) {
        if (balloon[0] > pos) {
            pos = balloon[1];
            ans++;
        }
    }
    return ans;
};